package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

/**
 * 对称的二叉树
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9828.%20%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91/README
 */
public class P28 {

    public static void main(String[] args) {
        TreeNode nod1 = new TreeNode(1);
        TreeNode nod2 = new TreeNode(2);
        TreeNode nod3 = new TreeNode(2);
        TreeNode nod4 = new TreeNode(3);
        TreeNode nod5 = new TreeNode(4);
        TreeNode nod6 = new TreeNode(4);
        TreeNode nod7 = new TreeNode(3);
        nod1.left = nod2;
        nod1.right = nod3;
        nod2.left = nod4;
        nod2.right = nod5;
        nod3.left = nod6;
        nod3.right = nod7;
        Solution solution = new P28().new Solution();
        boolean symmetric = solution.isSymmetric(nod1);
        System.out.println(symmetric);

    }

    /**
     * <img src="https://img-blog.csdnimg.cn/20190515202441659.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTAxOTE1,size_16,color_FFFFFF,t_70"/>
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isSymmetrical(root.left, root.right);
        }
        /**
         * 1.终止条件
         *     1.两个子树的节点为空时：说明则是对称的，返回true
         *     2.当输入的左右节点有一个为空，另一个不为空，他一定是不对称的，返回false；
         *     2.输入的左右节点值不同他也不是对称的，返回false；
         * 2.返回值
         *     当值相等时继续进行递归
         *     左子树的左节点=右子树的右节点 && 左子树的右节点=右子树的左节点
         */
        private boolean isSymmetrical(TreeNode left, TreeNode right) {
            if (left == null && right == null) {
                return true;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.value != right.value) {
                return false;
            }
            // 当值相等时继续进行递归
            return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);

        }
    }
}
